using System;
using System.Collections.Generic;
using System.Drawing;

namespace Nate.Pathfinding
{
    public class DepthFirst : Pathfinding.IPathfind
    {
        // 
        // Public Methods 
        //

        public void Init(NodeID start_id, NodeID dest_id, Graph graph)
        {
            _success     = false;
            _graph       = graph;
            _source      = start_id.GraphIndex;
            _destination = dest_id.GraphIndex;

            _stack       = new Stack<Edge>();
            _route       = new int[_graph.Nodes.Count];

            _stack.Push(new Edge(_source, _source));
        }

        public Shared.Status Tick()
        {
            if (_success)
            {
                return Shared.Status.Success;
            }

            if (_stack.Count > 0)
            {
                return _tick();
            }

            return Shared.Status.Failure;
        }

        // 
        // Public Properties 
        //

        public List<Point> Path
        {
            get
            {
                List<Point> path = new List<Point>();

                if (_success)
                {
                    // Let the caller see the path that was built.

                    int nodeID = _destination;
                    path.Add(_graph.Nodes[nodeID].Point);
                    while (nodeID != _source)
                    {
                        nodeID = _route[nodeID];
                        path.Add(_graph.Nodes[nodeID].Point);
                    }
                }
                else
                {
                    // While in progress let the caller see the nodes that 
                    // we've touched.

                    foreach (Node n in _graph.Nodes)
                    {
                        if (n.Visited)
                        {
                            path.Add(n.Point);
                        }
                    }
                }

                return path;
            }
        }

        public Nate.Shared.Utils.Options Options
        {
            get
            {
                return null;
            }
        }

        public string OptionSelection
        {
            set
            {
            }
        }

        //
        // Private Types
        //

        private struct Edge
        {
            public int To;
            public int From;
            
            public Edge(int to, int from)
            {
                To = to;
                From = from;
            }
        }

        // 
        // Private Data
        //

        // Nate-TODO: Make start/source and end/dest/destination/target consistant 
        // throughout the code. Annoying that it flops around.

        Stack<Edge> _stack;
        Graph       _graph;
        int[]       _route;
        int         _source;
        int         _destination;
        bool        _success;

        //
        // Private Methods
        //

        private Shared.Status _tick()
        {
            Edge edge = _stack.Pop();
            _route[edge.To] = edge.From;

            Node node = _graph.Nodes[edge.To];
            node.Visited = true;

            if (_destination == edge.To)
            {
                _success = true;
                return Shared.Status.Success;
            }

            foreach (Node neighbor in node.Neighbors.Values)
            {
                if (!neighbor.Visited)
                {
                    _stack.Push(new Edge(neighbor.Index, edge.To));
                }
            }

            return Shared.Status.InProcess;
        }
    }
}
